#include <iostream>
#include <vector>

using namespace std;

const int N = 1e4 + 10, INF = 2147483647;

typedef pair<int, int> PII;

int dist[N];
bool st[N];

vector<PII> edges[N];

int n, m, s;

void bellman_ford(int s)
{
	for(int i = 0; i <= n; i++) dist[i] = INF;
	dist[s] = 0;
	int cnt = 0;
	do
	{
		cnt = 0;
		for(int i = 1; i <= n; i++)
		{
			for(auto t : edges[i])
			{
				int b = t.first, c = t.second;
				if(dist[i] != INF && dist[i] + c < dist[b])
				{
					cnt++;
					dist[b] = dist[i] + c;
				}
			}
		}
	}while(cnt != 0);
	for(int i = 1; i <= n; i++) cout << dist[i] << " ";
}

int main()
{
	cin >> n >> m >> s;
	for(int i = 1; i <= m; i++)
	{
		int u, v, w; cin >> u >> v >> w;
		
		edges[u].push_back({v, w});
	}
	
	bellman_ford(s);
	return 0;
}

